package com.datastructure.linkedLit;

import java.security.Key;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 力扣链表解题  困难先不做
 *
 * @author chenzhihua
 * @Date 2024/7/23
 */
public class LikouProblem {
    public static void main(String[] args) {
        // 1,4,3,2,5,2
        ListNode listNode1 = new ListNode(1);
        ListNode listNode11 = new ListNode(2);
        ListNode listNode12 = new ListNode(3);
        ListNode listNode2 = new ListNode(4);
        ListNode listNode3 = new ListNode(5);
        listNode1.next = listNode11;
        listNode11.next = listNode12;
        listNode12.next = listNode2;
        listNode2.next = listNode3;
        ListNode listNode = reverseList(listNode1);
        playLinkedList(listNode);
    }

    // 打印链表
    public static void playLinkedList(ListNode listNode) {
        while (listNode != null) {
            System.out.print(listNode.val + "，");
            listNode = listNode.next;
        }
        System.out.println();
    }

    /**
     * 2. 两数相加
     * 中等
     * 问题: 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * 解题思路: 因为每位数字是逆序，所以最前面是个位数
     * 验证数据：
     * 输入：l1 = [2,4,3], l2 = [5,6,4]
     * 输出：[7,0,8]
     * 解释：342 + 465 = 807.
     * 示例 2：
     * 输入：l1 = [0], l2 = [0]
     * 输出：[0]
     * 示例 3：
     * 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
     * 输出：[8,9,9,9,0,0,0,1]
     * ListNode listNode = new ListNode(9);
     * ListNode listNode1 = new ListNode(9);
     * ListNode listNode2 = new ListNode(9);
     * ListNode listNode3 = new ListNode(9);
     * ListNode listNode4 = new ListNode(9);
     * ListNode listNode5 = new ListNode(9);
     * ListNode listNode6 = new ListNode(9);
     * listNode.next = listNode1;
     * listNode1.next = listNode2;
     * listNode2.next = listNode3;
     * listNode3.next = listNode4;
     * listNode4.next = listNode5;
     * listNode5.next = listNode6;
     * ListNode listNode10 = new ListNode(9);
     * ListNode listNode11 = new ListNode(9);
     * ListNode listNode12 = new ListNode(9);
     * ListNode listNode13 = new ListNode(9);
     * listNode10.next = listNode11;
     * listNode11.next = listNode12;
     * listNode12.next = listNode13;
     * ListNode listNode7 = addTwoNumbers(listNode, listNode10);
     * playLinkedList(listNode7);
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // l1链表得头节点
        ListNode p1 = l1;
        // l2链表得头节点
        ListNode p2 = l2;
        // 结果链表
        ListNode result = new ListNode();
        // 结果链表的头节点
        ListNode head = result;
        // 是否存在进位
        int carry = 0;
        int temp = 0;
        // 如果两个都存在值就进行相加
        while (p1 != null && p2 != null) {
            // 存在进位
            if (carry > 0) {
                // 获取相加后的个位数
                temp = (p1.val + p2.val + carry) % 10;
                // 获取进位
                carry = (p1.val + p2.val + carry) / 10;
            } else {
                temp = (p1.val + p2.val) % 10;
                carry = (p1.val + p2.val) / 10;
            }
            // 计算过的节点向后移
            p1 = p1.next;
            p2 = p2.next;
            // 创建新节点
            ListNode listNode = new ListNode(temp);
            head.next = listNode;
            head = head.next;
        }
        // 如果两个链表长度不一致需要继续添加(以下的判断只会有一种情况出现)
        while (p1 != null) {
            if (carry > 0) {
                // 获取相加后的个位数
                temp = (p1.val + carry) % 10;
                // 获取进位
                carry = (p1.val + carry) / 10;
            } else {
                temp = (p1.val) % 10;
                carry = (p1.val) / 10;
            }
            // 计算过的节点向后移
            p1 = p1.next;
            // 创建新节点
            ListNode listNode = new ListNode(temp);
            head.next = listNode;
            head = head.next;
        }
        while (p2 != null) {
            if (carry > 0) {
                // 获取相加后的个位数
                temp = (p2.val + carry) % 10;
                // 获取进位
                carry = (p2.val + carry) / 10;
            } else {
                temp = (p2.val) % 10;
                carry = (p2.val) / 10;
            }
            // 计算过的节点向后移
            p2 = p2.next;
            // 创建新节点
            ListNode listNode = new ListNode(temp);
            head.next = listNode;
            head = head.next;
        }
        // 如果链表最后一位也是0，并且还有进位
        if (carry != 0) {
            ListNode listNode = new ListNode(carry);
            head.next = listNode;
        }
        return result.next;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     * 中等
     * 问题： 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * 思路: 使用快慢指针，第一个快指针先移动到第n个节点的位置，然后快慢指针同时移动，直到快指针到达最后，慢指针到达的位置是需要移除节点的上一个
     * 验证数据：
     * 示例 1：
     * 输入：head = [1,2,3,4,5], n = 2
     * 输出：[1,2,3,5]
     * 示例 2：
     * 输入：head = [1], n = 1
     * 输出：[]
     * 示例 3：
     * 输入：head = [1,2], n = 1
     * 输出：[1]
     * ListNode listNode = new ListNode(1);
     * ListNode listNode1 = new ListNode(2);
     * ListNode listNode2 = new ListNode(3);
     * ListNode listNode3 = new ListNode(4);
     * ListNode listNode4 = new ListNode(5);
     * listNode.next = listNode1;
     * listNode1.next = listNode2;
     * listNode2.next = listNode3;
     * listNode3.next = listNode4;
     * ListNode listNode7 = removeNthFromEnd(listNode, 2);
     * playLinkedList(listNode7);
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 先转成存在一个头节点的链表
        ListNode preNode = new ListNode(0);
        preNode.next = head;

        // 新建两个节点来指向头节点
        ListNode start = preNode;
        ListNode end = preNode;
        // start指向第n个节点
        while (n != 0) {
            start = start.next;
            n--;
        }
        // 两个节点一起移动,直到start到达最后一个节点，end刚好到达倒数第n个的前一个
        while (start != null && start.next != null) {
            start = start.next;
            end = end.next;
        }
        // 根据end指针删除后面一个节点
        end.next = end.next.next;
        return preNode.next;
    }

    /**
     * 21. 合并两个有序链表
     * 简单
     * 问题： 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * 思路：因为头节点不确定首先先新建一个头节点，然后遍历两个链表，将小的添加到一个新的链表种
     * 示例 1：
     * 输入：l1 = [1,2,4], l2 = [1,3,4]
     * 输出：[1,1,2,3,4,4]
     * 示例 2：
     * 输入：l1 = [], l2 = []
     * 输出：[]
     * 示例 3：
     * 输入：l1 = [], l2 = [0]
     * 输出：[0]
     * ListNode listNode1 = new ListNode(1);
     * ListNode listNode2 = new ListNode(2);
     * ListNode listNode3 = new ListNode(4);
     * listNode1.next = listNode2;
     * listNode2.next = listNode3;
     * <p>
     * ListNode listNode10 = new ListNode(1);
     * ListNode listNode11 = new ListNode(2);
     * ListNode listNode12 = new ListNode(3);
     * listNode10.next = listNode11;
     * listNode11.next = listNode12;
     * ListNode listNode = mergeTwoLists(listNode1, listNode10);
     * playLinkedList(listNode);
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 首先进行一个防御性编程
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 创建一个头节点
        ListNode result = new ListNode(0);
        // 创建一个头节点需要移动的节点
        ListNode head = result;
        // 遍历两个链表
        while (list1 != null && list2 != null) {
            // 比较两个链表的节点，因为是升序所以将小的存到结果中
            if (list1.val < list2.val) {
                head.next = list1;
                list1 = list1.next;
            } else {
                head.next = list2;
                list2 = list2.next;
            }
            head = head.next;
        }
        // 如果list1或者list2有一个还没遍历完就直接添加到head后面
        if (list1 != null) {
            head.next = list1;
        }
        if (list2 != null) {
            head.next = list2;
        }
        return result.next;
    }

    /**
     * 24. 两两交换链表中的节点 ============一开始不会的
     * 中等
     * 问题: 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     * 思路：使用双指针实现，只有当每次双指针指的值都不为null就交换
     * 示例 1：
     * 输入：head = [1,2,3,4]
     * 输出：[2,1,4,3]
     * 示例 2：
     * 输入：head = []
     * 输出：[]
     * 示例 3：
     * 输入：head = [1]
     * 输出：[1]
     * 提示：
     * 链表中节点的数目在范围 [0, 100] 内
     * 0 <= Node.val <= 100
     * <p>
     * ListNode listNode1 = new ListNode(1);
     * ListNode listNode2 = new ListNode(2);
     * ListNode listNode3 = new ListNode(3);
     * ListNode listNode4 = new ListNode(4);
     * listNode1.next = listNode2;
     * listNode2.next = listNode3;
     * listNode3.next = listNode4;
     * <p>
     * ListNode listNode = swapPairs(listNode1);
     * playLinkedList(listNode);
     */
    public static ListNode swapPairs(ListNode head) {
        // 因为头节点看可能变化，所有新加一个头节点
        ListNode result = new ListNode(0);
        result.next = head;
        ListNode temp = result;
        // 存在两个有效节点的时候才进行交换
        while (temp.next != null && temp.next.next != null) {
            // 获取待交换的两个节点
            ListNode p1 = temp.next;
            ListNode p2 = temp.next.next;
            // 交换这两个节点
            temp.next = p2;
            p1.next = p2.next;
            p2.next = p1;
            // 将需要交换节点的指针放在交换后的后一个节点
            temp = p1;
        }
        return result.next;
    }

    /**
     * 82. 删除排序链表中的重复元素 II
     * 中等
     * 题目： 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
     * 思路： 双指针实现，循环条件是当前指针的nex和nex的next不为null，如果这两个节点相等在进行一样的循环，不相等就当前指针下移
     * 示例 1：
     * 输入：head = [1,2,3,3,4,4,5]
     * 输出：[1,2,5]
     * 示例 2：
     * 输入：head = [1,1,1,2,3]
     * 输出：[2,3]
     * 提示：
     * 链表中节点数目在范围 [0, 300] 内
     * -100 <= Node.val <= 100
     * 题目数据保证链表已经按升序 排列
     * ListNode listNode1 = new ListNode(1);
     * ListNode listNode11 = new ListNode(1);
     * ListNode listNode12 = new ListNode(1);
     * ListNode listNode2 = new ListNode(2);
     * ListNode listNode3 = new ListNode(3);
     * ListNode listNode4 = new ListNode(4);
     * listNode1.next = listNode11;
     * listNode11.next = listNode12;
     * listNode12.next = listNode2;
     * listNode2.next = listNode3;
     * listNode3.next = listNode4;
     * ListNode listNode = deleteDuplicates(listNode1);
     * playLinkedList(listNode);
     */
    public static ListNode deleteDuplicates2(ListNode head) {
        // 创建一个头节点
        ListNode result = new ListNode(0);
        result.next = head;
        ListNode cur = result;
        // cur指向要比较的两个节点的上一个节点
        while (cur.next != null && cur.next.next != null) {
            // 比较临近节点是否一样
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return result.next;
    }

    /**
     * 83. 删除排序链表中的重复元素
     * 简单
     * 问题：给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
     * 思路：头节点不会改变，循环当前节点和当前节点的next不为null，只要相对就删除下一个，不相等就当前节点下移
     * 示例 1：
     * 输入：head = [1,1,2]
     * 输出：[1,2]
     * 示例 2：
     * 输入：head = [1,1,2,3,3]
     * 输出：[1,2,3]
     */
    public static ListNode deleteDuplicates(ListNode head) {
        // 因为头节点不会变化所以直接在原本的节点操作
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * 61. 旋转链表============一开始不会的
     * 中等
     * 问题：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
     * 思路：最后k个节点从后到前依次移动到前面,链表首尾连接找到分段点 链表长度 - k%链表长度，断开新的头节点）
     * 示例 1：
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[4,5,1,2,3]
     * 示例 2：
     * 输入：head = [0,1,2], k = 4
     * 输出：[2,0,1]
     * 提示：
     * 链表中节点的数目在范围 [0, 500] 内
     * -100 <= Node.val <= 100
     * 0 <= k <= 2 * 109
     */
    public static ListNode rotateRight(ListNode head, int k) {
        // 不需要旋转的情况
        if (head == null || head.next == null || k == 0) {
            return head;
        }

        // 首先先计算总节点个数，并让尾节点指向头节点
        int total = 1;
        ListNode cur = head;
        while (cur.next != null) {
            total++;
            cur = cur.next;
        }
        cur.next = head;
        // 到这里cur指向的是尾节点，找到分段点(k的前一个节点)
        for (int i = 0; i < total - k % total; i++) {
            cur = cur.next;
        }
        head = cur.next;
        cur.next = null;
        return head;
    }

    /**
     * 86. 分隔链表
     * 中等
     * 问题：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     * 思路：定义两个空链表，一个存储小于目标的节点，一个存储大于目标的节点
     * 你应当 保留 两个分区中每个节点的初始相对位置。
     * 示例 1：
     * 输入：head = [1,4,3,2,5,2], x = 3
     * 输出：[1,2,2,4,3,5]
     * 示例 2：
     * 输入：head = [2,1], x = 2
     * 输出：[1,2]
     */
    public static ListNode partition(ListNode head, int x) {
        ListNode lh = new ListNode(0);
        ListNode rh = new ListNode(0);
        ListNode l = lh;
        ListNode r = rh;
        while (head != null) {
            if (head.val < x) {
                l.next = head;
                l = l.next;
            } else {
                r.next = head;
                r = r.next;
            }
            head = head.next;
        }
        l.next = rh.next;
        r.next = null;
        return lh.next;
    }

    /**
     * 92. 反转链表 II
     * 中等
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * 思路：将要翻转的节点使用头插法插入到链表中
     * 示例 1：
     * 输入：head = [1,2,3,4,5], left = 2, right = 4
     * 输出：[1,4,3,2,5]
     * 示例 2：
     * 输入：head = [5], left = 1, right = 1
     * 输出：[5]
     */
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || left == right) {
            return head;
        }
        ListNode result = new ListNode(0);
        result.next = head;
        ListNode pre = result;
        // 先找到第一个要插入的节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        // 需要移动的是next的节点，著需要移动right - left次，因为循环从0开始
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return result.next;
    }

    /**
     * 141. 环形链表
     * 相关企业
     * 问题：给你一个链表的头节点 head ，判断链表中是否有环。
     * 思路： 快慢指针，慢指针一次移动一次，快指针一次移动两次，循环是快指针的next和next.next不为null，如果快慢指针相遇就有环
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     * 思路： 快慢指针，只要两个指针相遇就相遇就有环，只要一个的指针的next是null就不存在环
     * 示例 1：
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     * 示例 2：
     * 输入：head = [1,2], pos = 0
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     * 示例 3：
     * 输入：head = [1], pos = -1
     * 输出：false
     * 解释：链表中没有环。
     */
    public static boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    /**
     * 142. 环形链表 II
     * 中等
     * 问题：给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * 思路： 直接用hash，key是遍历后的节点，hash中存在就是起点
     * 不允许修改 链表。
     * 示例 1：
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：返回索引为 1 的链表节点
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     * 示例 2：
     * 输入：head = [1,2], pos = 0
     * 输出：返回索引为 0 的链表节点
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     * 示例 3：
     * 输入：head = [1], pos = -1
     * 输出：返回 null
     * 解释：链表中没有环。
     */
    public static ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        // 使用hash来处理
        Map<ListNode, Integer> map = new HashMap<>();
        int count = 0;
        while (head != null) {
            if (map.containsKey(head)) {
                return head;
            } else {
                map.put(head, count);
            }
            head = head.next;
            count++;
        }
        return null;
    }

    /**
     * 143. 重排链表
     * 中等
     * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     * L0 → L1 → … → Ln - 1 → Ln
     * 请将其重新排列后变为：
     * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
     * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * 示例 1：
     * 输入：head = [1,2,3,4]
     * 输出：[1,4,2,3]
     * 示例 2：
     * 输入：head = [1,2,3,4,5]
     * 输出：[1,5,2,4,3]
     */
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        // 线性表处理
        List<ListNode> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp);
            temp = temp.next;
        }
        int start = 0, end = list.size() - 1;
        while (start < end) {
            list.get(start).next = list.get(end);
            start++;
            if (start == end) {
                break;
            }
            list.get(end).next = list.get(start);
            end--;
        }
        list.get(start).next = null;
    }

    /**
     * 206. 反转链表
     * 简单
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * 示例 1：
     * 输入：head = [1,2,3,4,5]
     * 输出：[5,4,3,2,1]
     * 示例 2：
     * 输入：head = [1,2]
     * 输出：[2,1]
     * 示例 3：
     * 输入：head = []
     * 输出：[]
     */
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //使用头插法
//        ListNode result = new ListNode(0);
//        result.next = head;
//        ListNode pre = result;
//        ListNode cur = head;
//        ListNode next;
//        while (cur.next != null) {
//            next = cur.next;
//            cur.next = next.next;
//            next.next = pre.next;
//            pre.next = next;
//
//        }
//        return result.next;
        // 递归实现
        if (head == null || head.next == null) {
            return head;
        }
        ListNode listNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return listNode;
    }
}


